import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        System.out.println(new Solution().partition("a"));
    }
}

class Solution {
    public List<List<String>> partition(String s) {
        boolean[][] valid = getValid(s);
        List<List<String>> ans = new ArrayList<>();
        backtracking(s, valid, 0, new ArrayList<>(), ans);
        return ans;
    }

    boolean[][] getValid(String s) {
        boolean[][] valid = new boolean[s.length()][s.length()];
        for (int width = 1; width <= s.length(); width++) {
            for (int i = 0; i + width <= s.length(); i++) {
                int j = i + width - 1;
                valid[i][j] = width == 1 || s.charAt(i) == s.charAt(j) && (width == 2 || valid[i + 1][j - 1]);
            }
        }
        return valid;
    }

    void backtracking(String s, boolean[][] valid, int i, List<String> cur, List<List<String>> ans) {
        if (i == s.length()) {
            ans.add(new ArrayList<>(cur));
            return;
        }
        for (int j = i; j < s.length(); j++) {
            if (valid[i][j]) {
                cur.add(s.substring(i, j + 1));
                backtracking(s, valid, j + 1, cur, ans);
                cur.remove(cur.size() - 1);
            }
        }
    }
}